Symantec Visual Cafe for Java 2.5/symantec-visual-cafe-2.5-database-dev-edition.iso/Visual Cafe Pro v1.0/TUTORIAL.BIN/Bignum.class

Java Class File | 1997-01-30 | 24.6 KB | 1,679 lines

package symjava.lang;

import java.util.Random;

public final class Bignum extends Number {
   private static int[] smallPrimes = new int[51];
   public static final int ROUND_STATISTICAL = -1;
   public static final int NO_ROUNDING = 9;
   public static final int ROUND_ABOVE_5 = 5;
   public static final int ROUND_ABOVE_4 = 4;
   public static final int ROUND_ALWAYS = 0;
   private static final int MAXSCALE = 1073741823;
   private int[] value;
   private int scale;
   private boolean negative;
   private static int roundingValue;
   static final int SRADIX = 30;
   private static final int BASE = 1073741824;
   private static final long MASK = 1073741823L;
   public static final Bignum ZERO;
   public static final Bignum ONE;
   public static final Bignum TWO;

   public static void setRoundingOption(int val) {
      switch (val) {
         case -1:
            roundingValue = -1;
            return;
         case 0:
            roundingValue = 0;
            return;
         case 4:
            roundingValue = 4;
            return;
         case 5:
            roundingValue = 5;
            return;
         case 9:
            roundingValue = 9;
            return;
         default:
            if (val < 0 || val > 9) {
               throw new IllegalArgumentException("Attempt to set invalid RoundingOption");
            }
      }
   }

   public static int getRoundingOption() {
      return roundingValue;
   }

   public Bignum(String s) {
      this.init(s, -1);
   }

   public Bignum(String s, int scale) {
      verifyScale(scale);
      this.init(s, scale);
   }

   public Bignum(int x, int scale) {
      verifyScale(scale);
      if (x < 0) {
         this.negative = true;
         x *= -1;
         if (x < 0) {
            int[] v = new int[]{0, 2};
            this.value = v;
            this._setScale(scale);
            return;
         }
      } else {
         this.negative = false;
      }

      int digit0 = (int)((long)x & 1073741823L);
      long carry = (long)x >> 30;
      int digit1 = (int)(carry & 1073741823L);
      if (digit1 > 0) {
         int[] v = new int[]{digit0, digit1};
         this.value = v;
      } else {
         int[] v = new int[]{digit0};
         this.value = v;
      }

      this._setScale(scale);
   }

   public Bignum(int x) {
      this(x, 0);
   }

   public Bignum(long x, int scale) {
      verifyScale(scale);
      if (x < 0L) {
         this.negative = true;
         x *= -1L;
         if (x < 0L) {
            int[] v = new int[]{0, 0, 8};
            this.value = v;
            this._setScale(scale);
            return;
         }
      } else {
         this.negative = false;
      }

      int digit0 = (int)(x & 1073741823L);
      long carry = x >> 30;
      int digit1 = (int)(carry & 1073741823L);
      carry >>= 30;
      int digit2 = (int)(carry & 1073741823L);
      if (digit2 > 0) {
         int[] v = new int[]{digit0, digit1, digit2};
         this.value = v;
      } else if (digit1 > 0) {
         int[] v = new int[]{digit0, digit1};
         this.value = v;
      } else {
         int[] v = new int[]{digit0};
         this.value = v;
      }

      this._setScale(scale);
   }

   public Bignum(long x) {
      this(x, 0);
   }

   public Bignum(double x, int scale) {
      verifyScale(scale);
      Double d = new Double(x);
      this.init(d.toString(), scale);
   }

   public Bignum(Bignum x) {
      this.scale = x.scale;
      this.value = new int[x.value.length];
      System.arraycopy(x.value, 0, this.value, 0, this.value.length);
      this.negative = x.negative;
   }

   public Bignum(Bignum x, int scale) {
      verifyScale(scale);
      this.scale = x.scale;
      this.value = new int[x.value.length];
      System.arraycopy(x.value, 0, this.value, 0, this.value.length);
      this.negative = x.negative;
      if (this.scale != scale) {
         this._setScale(scale);
      }

   }

   public static Bignum createFromByteArray(byte[] byteArray) {
      Bignum r = new Bignum(0);
      r.scale = 0;
      r.negative = false;
      r.value = new int[byteArray.length / 4 + 2];
      long carry = 0L;

      for(int i = 0; i < byteArray.length; ++i) {
         int c = byteArray[i] & 255;
         carry = (long)c;

         for(int k = 0; k < r.value.length; ++k) {
            long di = (long)r.value[k];
            r.value[k] = (int)((di << 8 | carry) & 1073741823L);
            carry = di >> 22;
         }

         if (carry != 0L) {
            r.value[r.value.length - 1] = (int)(carry & 1073741823L);
         }
      }

      return r;
   }

   public byte[] toByteArray() {
      int i = this.significantBits();
      if (i <= 0) {
         byte[] b = new byte[]{0};
      }

      int j = i / 8;
      if (i % 8 > 0) {
         ++j;
      }

      byte[] outArray = new byte[j];
      int[] r = new int[this.value.length];
      System.arraycopy(this.value, 0, r, 0, this.value.length);

      for(int var8 = outArray.length - 1; var8 >= 0; --var8) {
         outArray[var8] = (byte)(r[0] & 255);
         int carry = 0;

         for(int var7 = this.value.length - 1; var7 >= 0; --var7) {
            int val = r[var7];
            r[var7] = val >>> 8 | carry;
            carry = (int)((long)(val << 22) & 1073741823L);
         }
      }

      return outArray;
   }

   public static Bignum createFromIntegerArray(int[] intArray) {
      int[] t1 = new int[intArray.length + 1];

      for(int i = 0; i < intArray.length; ++i) {
         t1[i] = (int)((long)intArray[i] & 1073741823L);
      }

      Bignum r = new Bignum(t1);
      r.scale = 0;
      r.negative = false;
      return r;
   }

   public static Bignum createFromScaled(long scaled, int s) {
      verifyScale(s);
      Bignum n = new Bignum(scaled);
      if (s != 0) {
         n.scale = s;
      }

      return n;
   }

   public static Bignum createFromRadixString(String s, int radix) {
      Bignum r = new Bignum(0);
      r.scale = 0;
      r.negative = false;
      r.value = new int[s.length() / (radix / 2) + 1];
      boolean gotFirstDigit = false;

      for(int i = 0; i < s.length(); ++i) {
         char c = s.charAt(i);
         int a = Character.digit(c, radix);
         if (a >= 0) {
            gotFirstDigit = true;
            int[] t1 = mulAndAdd(r.value, radix, a);
            if (t1 != null) {
               r.value = t1;
            }
         } else if (c == '-' && !gotFirstDigit) {
            r.negative = true;
         }
      }

      return r;
   }

   public static Bignum random(int bits, Random randomSeed) {
      int ni = (bits - 1) / 30 + 1;
      bits %= 30;
      int[] rs = new int[ni];

      for(int i = 0; i < ni; ++i) {
         int r = (int)((long)randomSeed.nextInt() & 1073741823L);
         rs[i] = r;
      }

      rs[ni - 1] &= (1 << bits) - 1;
      Bignum rslt = new Bignum(rs);
      rslt.dropLeadingZeroes();
      return rslt;
   }

   public int intValue() {
      return (int)this.longValue();
   }

   public long longValue() {
      Bignum temp = new Bignum(this);
      temp._setScale(0);
      long lv = 0L;

      for(int i = temp.value.length < 3 ? temp.value.length - 1 : 2; i >= 0; --i) {
         lv = (lv << 30) + (long)temp.value[i];
      }

      return temp.negative ? -lv : lv;
   }

   public float floatValue() {
      return (float)this.doubleValue();
   }

   public double doubleValue() {
      Bignum temp = new Bignum(this);
      temp._setScale(0);
      double d = (double)0.0F;
      int m = this.value.length - 1;
      m = m > 4 ? m - 4 : 0;

      for(int i = this.value.length - 1; i >= m; --i) {
         d = d * 1.073741823E9 + (double)this.value[i];
      }

      if (m > 0) {
         d *= Math.pow((double)30.0F, (double)m);
      }

      this.subtract(temp);
      if (this.scale != 0) {
         double s = (double)1.0F;
         s = Math.pow((double)10.0F, (double)this.scale);
         d /= s;
      }

      return this.negative ? -d : d;
   }

   public String toString() {
      if (this.value == null) {
         return "null";
      } else {
         int l = this.value.length * 10 + 2;
         if (l < this.scale) {
            l = this.scale + 2;
         }

         char[] x = new char[l];
         int xi = x.length - 1;
         int dp = xi - this.scale;
         if (this.scale == 0) {
            dp = -9999;
         }

         int[] temp = new int[this.value.length];
         System.arraycopy(this.value, 0, temp, 0, temp.length);
         int i = temp.length - 1;

         while(i >= 0) {
            if (temp[i] == 0) {
               --i;
            } else {
               int rem = div0(temp, temp, 10);
               x[xi--] = Character.forDigit(rem, 10);
               if (xi == dp) {
                  --xi;
               }
            }
         }

         if (xi == x.length - 1) {
            x[xi--] = '0';
         }

         if (dp > 0) {
            while(xi > dp) {
               x[xi--] = '0';
            }

            x[dp] = '.';
         }

         String ms = this.negative ? "-" : "";
         ms = ms + (new String(x, xi, x.length - xi)).trim();
         return ms;
      }
   }

   public String toString(int radix) {
      if (radix == 10) {
         return this.toString();
      } else if (this.value == null) {
         return "null";
      } else {
         StringBuffer sb = new StringBuffer();
         int[] temp = new int[this.value.length];
         int len = 0;
         System.arraycopy(this.value, 0, temp, 0, temp.length);
         int i = temp.length - 1;

         while(i >= 0) {
            if (temp[i] == 0) {
               --i;
            } else {
               int rem = div0(temp, temp, radix);
               sb.insert(0, Character.forDigit(rem, radix));
               ++len;
            }
         }

         if (len == 0) {
            sb.insert(0, '0');
         }

         String ms = this.negative ? "-" : "";
         ms = ms + sb.toString().trim();
         return ms;
      }
   }

   public int getScale() {
      return this.scale;
   }

   public Bignum add(Bignum n) {
      Bignum result = new Bignum(this);
      Bignum x;
      if (this.scale != n.scale) {
         x = new Bignum(n);
         x._setScale(this.scale);
      } else {
         x = n;
      }

      if (result.negative == x.negative) {
         result.value = add0(result.value, x.value);
         return result;
      } else if (!result.negative) {
         int cmp = result.compareAbs(x);
         if (cmp < 0) {
            result = x.subtract(this);
            result.negative = x.negative;
            return result;
         } else if (cmp > 0) {
            result = result.subtract(x);
            return result;
         } else {
            result.zero();
            return result;
         }
      } else {
         int cmp = result.compareAbs(x);
         if (cmp < 0) {
            result = x.subtract(this);
            result.negative = x.negative;
            return result;
         } else if (cmp > 0) {
            result = result.subtract(x);
            return result;
         } else {
            result.zero();
            return result;
         }
      }
   }

   public Bignum subtract(Bignum n) {
      Bignum result = new Bignum(this);
      Bignum x;
      if (this.scale != n.scale) {
         x = new Bignum(n);
         x._setScale(this.scale);
      } else {
         x = n;
      }

      if (!result.negative && !x.negative) {
         int c = result.compareAbs(x);
         if (c == 0) {
            result.zero();
            return result;
         } else if (c == 1) {
            result.value = sub0(this.value, x.value);
            return result;
         } else {
            result.value = sub0(x.value, this.value);
            result.negative = true;
            return result;
         }
      } else if (!result.negative && x.negative) {
         result.value = add0(result.value, x.value);
         return result;
      } else if (result.negative && !x.negative) {
         result.value = add0(result.value, x.value);
         return result;
      } else {
         int c = result.compareAbs(x);
         if (c == 0) {
            result.zero();
            return result;
         } else if (c == -1) {
            result.value = sub0(x.value, this.value);
            result.negative = false;
            return result;
         } else {
            result.value = sub0(this.value, x.value);
            result.negative = true;
            return result;
         }
      }
   }

   public Bignum multiply(Bignum x) {
      Bignum prod = new Bignum(this);
      prod.scale += x.scale;
      prod.negative = this.negative != x.negative;
      Bignum m;
      Bignum mx;
      if (this.value.length > x.value.length) {
         m = this;
         mx = x;
      } else {
         m = x;
         mx = this;
      }

      if (mx.value.length == 1) {
         prod.value = mul0(m.value, mx.value[0]);
      } else {
         prod.value = mul0(m.value, mx.value);
      }

      if (prod.scale != this.scale) {
         prod._setScale(this.scale);
      }

      prod.dropLeadingZeroes();
      return prod;
   }

   public Bignum divide(Bignum x) {
      if (x.compareAbs(ZERO) == 0) {
         throw new ArithmeticException("Division by zero");
      } else {
         Bignum dividend = new Bignum(this);
         Bignum divisor = new Bignum(x);
         dividend.dropLeadingZeroes();
         divisor.dropLeadingZeroes();
         if (roundingValue < 9 || divisor.scale > dividend.scale) {
            int scaleFactor = divisor.scale + 1;
            ++dividend.scale;
            int m1 = 9;
            int m4 = 1000000000;

            int x1;
            for(x1 = scaleFactor; x1 >= m1; x1 -= m1) {
               dividend.value = mul0(dividend.value, m4);
            }

            if (x1 > 0) {
               dividend.value = mul0(dividend.value, pow(10, x1));
            }
         }

         Bignum quot = new Bignum(new int[dividend.value.length - divisor.value.length + 1]);
         quot.negative = divisor.negative ? !dividend.negative : dividend.negative;
         quot.scale = dividend.scale;
         if (divisor.value.length == 1) {
            div0(quot.value, dividend.value, divisor.value[0]);
            quot._setScale(this.scale);
            return quot;
         } else {
            int vLeftmostDigit = divisor.value[divisor.value.length - 1];
            if (vLeftmostDigit >= 536870912) {
               int[] tvalue = new int[dividend.value.length + 1];
               System.arraycopy(dividend.value, 0, tvalue, 0, dividend.value.length);
               tvalue[tvalue.length - 1] = 0;
               dividend.value = tvalue;
               div(dividend, divisor, quot);
            } else {
               int[] tvalue = new int[dividend.value.length + 1];
               System.arraycopy(dividend.value, 0, tvalue, 0, dividend.value.length);
               int d = 1073741824 / (vLeftmostDigit + 1);
               dividend.value = mul0(tvalue, d);
               divisor.value = mul0(divisor.value, d);
               div(dividend, divisor, quot);
            }

            quot._setScale(this.scale);
            return quot;
         }
      }
   }

   public Bignum[] integerDivide(Bignum x) {
      if (x.compareAbs(ZERO) == 0) {
         throw new ArithmeticException("Division by zero");
      } else {
         Bignum dividend = new Bignum(this);
         Bignum divisor = new Bignum(x);
         Bignum quot = _intDivide(divisor, dividend, this.scale);
         Bignum[] r = new Bignum[]{quot, dividend};
         return r;
      }
   }

   private static Bignum _intDivide(Bignum divisor, Bignum dividend, int scale) {
      dividend.dropLeadingZeroes();
      divisor.dropLeadingZeroes();
      if (divisor.scale > dividend.scale) {
         int scaleFactor = divisor.scale;
         int m1 = 9;
         int m4 = 1000000000;

         int x1;
         for(x1 = scaleFactor; x1 >= m1; x1 -= m1) {
            dividend.value = mul0(dividend.value, m4);
         }

         if (x1 > 0) {
            dividend.value = mul0(dividend.value, pow(10, x1));
         }
      }

      if (dividend.lessThan(divisor)) {
         return new Bignum(0, 0);
      } else {
         Bignum quot = new Bignum(new int[dividend.value.length - divisor.value.length + 1]);
         quot.negative = divisor.negative ? !dividend.negative : dividend.negative;
         if (dividend.scale >= divisor.scale) {
            quot.scale = dividend.scale - divisor.scale;
         } else {
            quot.scale = 0;
         }

         if (divisor.value.length == 1) {
            int rem = div0(quot.value, dividend.value, divisor.value[0]);
            dividend.zero();
            dividend.value[0] = (int)((long)rem & 1073741823L);
            long carry = (long)rem >> 30;
            int digit1 = (int)(carry & 1073741823L);
            if (digit1 > 0) {
               if (dividend.value.length < 2) {
                  int[] newval = new int[]{dividend.value[0], digit1};
                  dividend.value = newval;
               } else {
                  dividend.value[1] = digit1;
               }
            }

            return quot.scale > 0 ? truncate(quot) : quot;
         } else {
            int vLeftmostDigit = divisor.value[divisor.value.length - 1];
            if (vLeftmostDigit >= 536870912) {
               int[] tvalue = new int[dividend.value.length + 1];
               System.arraycopy(dividend.value, 0, tvalue, 0, dividend.value.length);
               tvalue[tvalue.length - 1] = 0;
               dividend.value = tvalue;
               div(dividend, divisor, quot);
            } else {
               int[] tvalue = new int[dividend.value.length + 1];
               System.arraycopy(dividend.value, 0, tvalue, 0, dividend.value.length);
               int d = 1073741824 / (vLeftmostDigit + 1);
               dividend.value = mul0(tvalue, d);
               divisor.value = mul0(divisor.value, d);
               div(dividend, divisor, quot);
               div0(dividend.value, dividend.value, d);
            }

            if (quot.scale > 0) {
               quot = truncate(quot);
            }

            return quot;
         }
      }
   }

   public Bignum remainder(Bignum x) {
      if (x.compareAbs(ZERO) == 0) {
         throw new ArithmeticException("Division by zero");
      } else if (this.lessThan(x)) {
         return new Bignum(this);
      } else {
         Bignum dividend = new Bignum(this);
         Bignum divisor = new Bignum(x);
         _intDivide(divisor, dividend, this.scale);
         return dividend;
      }
   }

   public Bignum sqrt() {
      Bignum g = new Bignum(this, this.scale + 1);
      Bignum temp = new Bignum(0);
      div0(g.value, g.value, 2);
      Bignum eps = createFromScaled(5L, g.scale);

      for(Bignum diff = g.multiply(g).subtract(this); diff.compareAbs(eps) > 0; diff = temp.subtract(this)) {
         temp.value = mul0(g.value, 2);
         temp.scale = g.scale;
         temp.negative = g.negative;
         temp = diff.divide(temp);
         g = g.subtract(temp);
         temp = g.multiply(g);
      }

      return g;
   }

   public Bignum pow(int e) {
      if (e == 0) {
         return new Bignum((double)1.0F, this.scale);
      } else {
         Bignum ans = new Bignum(this);

         int[] t;
         for(t = new int[]{1}; e > 1; e >>= 1) {
            if ((e & 1) == 1) {
               t = mul0(t, ans.value);
            }

            ans.value = mul0(ans.value, ans.value);
         }

         ans.value = mul0(ans.value, t);
         ans.dropLeadingZeroes();
         return ans;
      }
   }

   public boolean equals(Object obj) {
      Bignum x = (Bignum)obj;
      return this.compare(x) == 0;
   }

   public boolean lessThan(Bignum x) {
      return this.compare(x) == -1;
   }

   public boolean lessThanOrEquals(Bignum x) {
      return this.compare(x) != 1;
   }

   public boolean greaterThan(Bignum x) {
      return this.compare(x) == 1;
   }

   public boolean greaterThanOrEquals(Bignum x) {
      return this.compare(x) != -1;
   }

   public int hashCode() {
      int hash = 0;

      for(int i = 0; i < this.value.length; ++i) {
         try {
            hash += this.value[i];
         } catch (Exception var3) {
            hash = 0;
         }
      }

      return hash;
   }

   public Bignum setScale(int scale) {
      verifyScale(scale);
      Bignum x = new Bignum(this, scale);
      return x;
   }

   public int significantBits() {
      int i;
      for(i = this.value.length - 1; i >= 0 && this.value[i] == 0; --i) {
      }

      if (i < 0) {
         return 0;
      } else {
         int val = this.value[i];

         for(i = 0; val != 0; ++i) {
            val >>>= 1;
         }

         int var5 = i * 30;
         return var5 + i;
      }
   }

   public Bignum shiftRight(int shiftBits) {
      if (shiftBits < 0) {
         throw new IllegalArgumentException("Number of bits to shift may not be negative");
      } else {
         int nw = shiftBits / 30;
         shiftBits %= 30;
         int[] r = new int[this.value.length - nw];
         System.arraycopy(this.value, nw, r, 0, this.value.length - nw);
         int carry = 0;

         for(int i = r.length - 1; i >= 0; --i) {
            int val = r[i];
            r[i] = val >>> shiftBits | carry;
            carry = (int)((long)(val << 30 - shiftBits) & 1073741823L);
         }

         Bignum result = new Bignum(r);
         result.dropLeadingZeroes();
         return result;
      }
   }

   public Bignum shiftLeft(int shiftBits) {
      if (shiftBits < 0) {
         throw new IllegalArgumentException("Number of bits to shift may not be negative");
      } else {
         int nw = shiftBits / 30;
         shiftBits %= 30;
         int[] r = new int[this.value.length + nw + 1];
         System.arraycopy(this.value, 0, r, nw, this.value.length);
         int carry = 0;

         for(int i = 0; i < r.length - 1; ++i) {
            int val = r[i];
            r[i] = (int)((long)(val << shiftBits) | (long)carry & 1073741823L);
            carry = val >>> 30 - shiftBits;
         }

         if (carry != 0) {
            r[r.length - 1] = carry;
         }

         Bignum result = new Bignum(r);
         result.dropLeadingZeroes();
         return result;
      }
   }

   public Bignum modInverse(Bignum mod) {
      Bignum i = new Bignum(mod);
      Bignum h = new Bignum(this);
      Bignum v = new Bignum(ZERO);

      Bignum x;
      for(Bignum d = new Bignum(1); h.greaterThan(ZERO); v = x) {
         Bignum[] tt = i.integerDivide(h);
         Bignum t = tt[0];
         x = h;
         h = i.subtract(t.multiply(h));
         i = x;
         x = d;
         d = v.subtract(t.multiply(d));
      }

      if (!v.negative) {
         return v.remainder(mod);
      } else {
         Bignum m = v.remainder(mod).multiply(mod);
         return v.subtract(m);
      }
   }

   public Bignum modExp(Bignum exponent, Bignum mod) {
      int ipr = exponent.significantBits() - 1;
      int ibit = 1 << ipr % 30;
      ipr /= 30;
      int[] t = new int[this.value.length + 1];
      Bignum rslt = new Bignum(ONE);

      while(ipr >= 0) {
         rslt.value = mul0(rslt.value, rslt.value, t);
         if (rslt.value != t) {
            t = rslt.value;
         }

         rslt = rslt.remainder(mod);
         if ((exponent.value[ipr] & ibit) != 0) {
            for(int i = 0; i < t.length; ++i) {
               t[i] = 0;
            }

            rslt.value = mul0(rslt.value, this.value, t);
            if (rslt.value != t) {
               t = rslt.value;
            }

            rslt = rslt.remainder(mod);
         }

         ibit >>>= 1;
         if (ibit == 0) {
            --ipr;
            ibit = 536870912;
         }

         for(int i = 0; i < t.length; ++i) {
            t[i] = 0;
         }
      }

      return rslt;
   }

   public boolean isProbablePrime() {
      if ((this.value[0] & 1) != 1) {
         return this.equals(TWO);
      } else {
         for(int i = 1; i < 11; ++i) {
            int prime = smallPrimes[i];
            if (this.quickMod(prime) == 0 && this.value[0] != prime) {
               return false;
            }
         }

         return this.isProbablePrime0(50);
      }
   }

   private int quickMod(int d) {
      int rem = 0;

      long temp;
      for(int i = this.value.length; i-- > 0; rem = (int)(temp % (long)d)) {
         temp = (long)(this.value[i] << 32 | rem);
      }

      if (this.negative && rem != 0) {
         rem = d - rem;
      }

      return rem;
   }

   private boolean isProbablePrime0(int n) {
      Bignum wm1 = this.subtract(ONE);
      int a = 0;
      int l = 0;

      for(int i = 0; i < wm1.value.length && wm1.value[i] == 0; ++i) {
         ++l;
      }

      for(int val = wm1.value[l]; (val & 1) == 0; val >>>= 1) {
         ++a;
      }

      a = l * 30 + a;
      if (a == 0) {
         return false;
      } else {
         Bignum m = wm1.shiftRight(a);
         Bignum z = new Bignum(3);
         z = z.modExp(m, this);
         if (!z.equals(ONE) && !z.equals(wm1)) {
            for(int j = 1; j < a; ++j) {
               z = z.multiply(z);
               z = z.remainder(this);
               if (z.equals(wm1)) {
                  return true;
               }

               if (z.equals(ONE)) {
                  return false;
               }
            }

            int s = wm1.significantBits();

            for(int i = 0; i < n; ++i) {
               Bignum b = random(s, new Random());
               if (b.greaterThan(wm1)) {
                  b = b.remainder(wm1);
               }

               z = b.modExp(m, this);
               if (!z.equals(ONE) && !z.equals(wm1)) {
                  int var14;
                  for(var14 = 1; var14 < a; ++var14) {
                     z = z.modExp(TWO, this);
                     if (z.equals(wm1)) {
                        break;
                     }

                     if (z.equals(ONE)) {
                        return false;
                     }
                  }

                  if (var14 == a) {
                     return false;
                  }
               }
            }

            return true;
         } else {
            return true;
         }
      }
   }

   private static void verifyScale(int scale) {
      if (scale < 0) {
         throw new IllegalArgumentException("Scale is negative");
      } else if (scale > 1073741823) {
         throw new IllegalArgumentException("Scale greater than maximum scale");
      }
   }

   public int compare(Bignum B) {
      if (!this.negative && !B.negative) {
         return this.compareAbs(B);
      } else if (this.negative && !B.negative) {
         return -1;
      } else if (!this.negative && B.negative) {
         return 1;
      } else {
         int r = this.compareAbs(B);
         if (r != 0) {
            r *= -1;
         }

         return r;
      }
   }

   private int compareAbs(Bignum A) {
      Bignum B;
      if (A.scale == this.scale) {
         B = A;
      } else {
         B = new Bignum(A, this.scale);
      }

      int sigB;
      for(sigB = B.value.length - 1; sigB > 0 && B.value[sigB] == 0; --sigB) {
      }

      ++sigB;

      int sigA;
      for(sigA = this.value.length - 1; sigA > 0 && this.value[sigA] == 0; --sigA) {
      }

      ++sigA;
      if (sigA > sigB) {
         return 1;
      } else if (sigB > sigA) {
         return -1;
      } else if (sigA == 0 && sigB == 0) {
         return 0;
      } else {
         do {
            --sigA;
            if (sigA < 0) {
               return 0;
            }

            if (this.value[sigA] > B.value[sigA]) {
               return 1;
            }
         } while(this.value[sigA] >= B.value[sigA]);

         return -1;
      }
   }

   private void init(String s, int iscale) {
      boolean scaleGiven = true;
      this.scale = 0;
      int mantVal = 0;
      if (iscale < 0) {
         scaleGiven = false;
      }

      int inScale = 0;
      this.negative = false;
      if (scaleGiven) {
         this.value = new int[(s.length() + iscale) / 3 + 1];
      } else {
         this.value = new int[s.length() / 5 + 1];
      }

      int[] t1 = new int[]{10};
      boolean mant = false;
      boolean gotFirstDigit = false;
      boolean gotFirstExpDigit = false;

      for(int i = 0; i < s.length(); ++i) {
         char c = s.charAt(i);
         if (c >= '0' && c <= '9') {
            if (inScale != 0 && !mant) {
               ++inScale;
            }

            int a = Character.digit(c, 10);
            if (mant) {
               mantVal = mantVal * 10 + a;
               gotFirstExpDigit = true;
            } else {
               t1 = mulAndAdd(this.value, 10, a);
               if (t1 != null) {
                  this.value = t1;
               }

               gotFirstDigit = true;
            }
         } else if (c == '-') {
            if (mant) {
               if (!gotFirstExpDigit) {
                  mantVal = -mantVal;
               }
            } else if (!gotFirstDigit) {
               this.negative = true;
            }
         } else {
            if (c == '.' && inScale == 0) {
               inScale = 1;
            }

            if (c == 'E' || c == 'e') {
               mant = true;
            }
         }
      }

      if (mant) {
         if (inScale != 0) {
            this.scale = inScale - 1;
         } else {
            this.scale = 0;
         }

         if (mantVal < 0) {
            mantVal *= -1;
            this.divide((new Bignum(10, 0)).pow(mantVal));
         } else {
            this.value = mul0(this.value, (new Bignum(10, 0)).pow(mantVal).value);
         }

         if (scaleGiven) {
            this._setScale(iscale);
         }

      } else {
         if (inScale != 0) {
            --inScale;
            this.scale = inScale;
            if (scaleGiven && this.scale != iscale) {
               this._setScale(iscale);
               return;
            }
         } else {
            this.scale = 0;
            if (scaleGiven) {
               this._setScale(iscale);
            }
         }

      }
   }

   private void zero() {
      this.negative = false;

      for(int i = 0; i < this.value.length; ++i) {
         this.value[i] = 0;
      }

   }

   private void dropLeadingZeroes() {
      int i;
      for(i = this.value.length - 1; i >= 0 && this.value[i] == 0; --i) {
      }

      if (i < 0) {
         i = 0;
      }

      ++i;
      if (i < this.value.length) {
         int[] nval = new int[i];
         System.arraycopy(this.value, 0, nval, 0, i);
         this.value = nval;
      }
   }

   public static Bignum truncate(Bignum in) {
      if (in.scale == 0) {
         return new Bignum(in);
      } else {
         int scaleFactor = in.scale - 1;
         int[] tval = new int[1];
         tval[0] = 0;
         int m1 = 9;
         int m4 = 1000000000;

         int x;
         for(x = scaleFactor; x >= m1; x -= m1) {
            tval = mul0(tval, m4);
         }

         if (x > 0) {
            tval = mul0(tval, pow(10, x));
         }

         tval = add0(in.value, tval);

         for(x = scaleFactor + 1; x >= m1; x -= m1) {
            div0(tval, tval, m4);
         }

         if (x > 0) {
            div0(tval, tval, pow(10, x));
         }

         Bignum out = new Bignum(tval);
         out.scale = 0;
         out.negative = in.negative;
         return out;
      }
   }

   private void _setScale(int iscale) {
      verifyScale(iscale);
      if (iscale != this.scale) {
         if (iscale > this.scale) {
            for(int i = iscale - this.scale; i > 0; --i) {
               this.value = mul0(this.value, 10);
            }

            this.scale = iscale;
         } else {
            int tempRoundingValue = roundingValue;
            if (roundingValue == -1) {
               tempRoundingValue = 9;
            }

            int scaleFactor = this.scale - iscale - 1;
            int[] tval = new int[]{9 - tempRoundingValue};
            int m1 = 9;
            int m4 = 1000000000;

            int x;
            for(x = scaleFactor; x >= m1; x -= m1) {
               tval = mul0(tval, m4);
            }

            if (x > 0) {
               tval = mul0(tval, pow(10, x));
            }

            this.value = add0(this.value, tval);

            for(x = scaleFactor + 1; x >= m1; x -= m1) {
               div0(this.value, this.value, m4);
            }

            if (x > 0) {
               div0(this.value, this.value, pow(10, x));
            }

            if (roundingValue == -1 && (this.value[0] & 1) == 1) {
               int var10002 = this.value[0]++;
            }

            this.scale = iscale;
         }
      }
   }

   private static int[] mul0(int[] u, int[] v) {
      int n = u.length - 1;
      int m = v.length - 1;
      long k = 0L;
      int[] w = new int[u.length + v.length];

      for(int j = 0; j <= n; ++j) {
         k = 0L;
         int q = j;

         for(int i = 0; i <= m; ++i) {
            long uv = (long)u[j];
            long t = uv * (long)v[i] + (long)w[q] + k;
            w[q++] = (int)(t & 1073741823L);
            k = t >> 30;
         }

         while(k != 0L) {
            long uv = (long)w[q] + k;
            w[q++] = (int)(uv & 1073741823L);
            k = uv >> 30;
         }
      }

      if (w[w.length - 1] != 0) {
         return w;
      } else {
         int ul;
         for(ul = w.length - 1; ul > 0 && w[ul] == 0; --ul) {
         }

         ++ul;
         int[] w1 = new int[ul];
         System.arraycopy(w, 0, w1, 0, w1.length);
         return w1;
      }
   }

   private static int[] mul0(int[] u, int v) {
      int n = u.length - 1;
      long k = 0L;
      long x = (long)v & 1073741823L;
      int[] w = new int[u.length];
      if (x != 0L) {
         for(int i = 0; i <= n; ++i) {
            long uv = ((long)u[i] & 1073741823L) * x + k;
            w[i] = (int)(uv & 1073741823L);
            k = uv >> 30;
         }

         if (k != 0L) {
            int[] ww = new int[w.length + 1];
            System.arraycopy(w, 0, ww, 0, w.length);
            ww[ww.length - 1] = (int)k;
            w = ww;
         }
      }

      return w;
   }

   private static int[] add0(int[] u, int[] v) {
      int j = 0;

      int ul;
      for(ul = u.length - 1; ul > 0 && u[ul] == 0; --ul) {
      }

      int vl;
      for(vl = v.length - 1; vl > 0 && v[vl] == 0; --vl) {
      }

      ++ul;
      ++vl;
      if (ul < vl) {
         int[] temp = u;
         u = v;
         v = temp;
         int temp2 = ul;
         ul = vl;
         vl = temp2;
      }

      int[] w = new int[ul + 1];
      long carry = 0L;

      for(j = 0; j < vl; ++j) {
         long temp = (long)(u[j] + v[j]) + carry;
         carry = temp >> 30;
         w[j] = (int)(temp & 1073741823L);
      }

      while(carry != 0L && j < ul) {
         long temp = (long)u[j] + carry;
         w[j] = (int)(temp & 1073741823L);
         carry = temp >> 30;
         ++j;
      }

      if (carry == 0L && j < ul) {
         while(j < ul) {
            w[j] = u[j];
            ++j;
         }
      } else {
         w[j] = (int)(carry & 1073741823L);
      }

      return w;
   }

   private static int[] add0(int[] u, int v) {
      int j = 0;

      int ul;
      for(ul = u.length - 1; ul > 0 && u[ul] == 0; --ul) {
      }

      int[] w = new int[ul++ + 1];
      long carry = 0L;
      long temp = ((long)u[j] & 1073741823L) + ((long)v & 1073741823L);
      carry = temp >> 30;
      w[j] = (int)(temp & 1073741823L);
      ++j;

      while(carry != 0L && j < ul) {
         temp = (long)u[j] + carry;
         w[j] = (int)(temp & 1073741823L);
         carry = temp >> 30;
         ++j;
      }

      if (carry == 0L && j < ul) {
         while(j < ul) {
            w[j] = u[j];
            ++j;
         }
      }

      return w;
   }

   private static int[] sub0(int[] u, int[] v) {
      boolean borrow = false;

      int ul;
      for(ul = u.length - 1; ul > 0 && u[ul] == 0; --ul) {
      }

      int vl;
      for(vl = v.length - 1; vl > 0 && v[vl] == 0; --vl) {
      }

      int[] w = new int[ul + 1];

      int wj;
      int j;
      for(j = 0; j <= vl; borrow = wj < 0) {
         wj = u[j] - v[j] + (borrow ? -1 : 0);
         w[j++] = (int)((long)wj & 1073741823L);
      }

      if (borrow) {
         while(j <= ul) {
            w[j] = u[j] - (borrow ? 1 : 0);
            if (w[j++] >= 0) {
               break;
            }
         }
      }

      while(j <= ul) {
         w[j] = u[j];
         ++j;
      }

      return w;
   }

   private static int div0(int[] quotient, int[] dividend, int divisor) {
      long carry = 0L;

      for(int i = dividend.length - 1; i >= 0; --i) {
         long x = ((long)dividend[i] & 1073741823L) + (carry << 30);
         quotient[i] = (int)(x / ((long)divisor & 1073741823L));
         carry = x % (long)divisor;
      }

      return (int)carry;
   }

   private static void div(Bignum dvdnd, Bignum div, Bignum quot) {
      int divlen = div.value.length - 1;
      int d1 = div.value[divlen];
      int d2 = div.value[divlen - 1];
      int[] dndVal = dvdnd.value;
      int[] divVal = div.value;
      int qx = quot.value.length - 1;

      for(int j = dvdnd.value.length - 1; j > divlen; --j) {
         int dd0 = dndVal[j];
         int dd1 = dndVal[j - 1];
         int dd2 = dndVal[j - 2];
         long temp1 = ((long)dd0 << 30) + (long)dd1;
         long q;
         if (dd0 == d1) {
            q = 1073741823L;
         } else {
            q = temp1 / (long)d1;
         }

         while(true) {
            long p1 = (long)d2 * q;
            long p2 = temp1 - (long)d1 * q;
            p2 = (p2 << 30) + (long)dd2;
            if (p1 <= p2) {
               if (q == 0L) {
                  quot.value[qx--] = 0;
               } else {
                  int k = j - divlen - 1;
                  long carry = 0L;

                  for(int dk = 0; dk <= divlen; ++dk) {
                     long x1 = (long)divVal[dk] * q + carry;
                     int x2 = dndVal[k] - (int)(x1 & 1073741823L);
                     if (x2 < 0) {
                        dndVal[k++] = x2 + 1073741824;
                        carry = (x1 >> 30) + 1L;
                     } else {
                        dndVal[k++] = x2;
                        carry = x1 >> 30;
                     }
                  }

                  if (carry != 0L) {
                     int temp = dndVal[k] - (int)carry;
                     if (temp >= 0) {
                        dndVal[k] = temp;
                     } else {
                        dndVal[k] = temp + 1073741824;
                        carry = 0L;
                        k = j - divlen - 1;
                        --q;

                        for(int dk = 0; dk <= divlen; ++dk) {
                           long nv = (long)(divVal[dk] + dndVal[k]) + carry;
                           dndVal[k++] = (int)(nv & 1073741823L);
                           carry = nv >> 30;
                        }

                        if (carry == 1L) {
                           dndVal[k] = (int)((long)(dndVal[k] + 1) & 1073741823L);
                        }
                     }
                  }

                  quot.value[qx--] = (int)q;
               }
               break;
            }

            --q;
         }
      }

   }

   private static int pow(int b, int e) {
      if (e == 0) {
         return 1;
      } else if (e == 1) {
         return b;
      } else {
         int ans = b;

         int temp;
         for(temp = 1; e != 1; e >>= 1) {
            if ((e & 1) == 1) {
               temp *= ans;
            }

            ans *= ans;
         }

         return ans * temp;
      }
   }

   private static int[] mulAndAdd(int[] val, int m, int a) {
      int n = val.length - 1;
      long k = (long)a & 1073741823L;
      long x = (long)m & 1073741823L;
      int[] w = val;
      if (x != 0L) {
         for(int i = 0; i <= n; ++i) {
            long uv = ((long)val[i] & 1073741823L) * x + k;
            w[i] = (int)(uv & 1073741823L);
            k = uv >> 30;
         }

         if (k != 0L) {
            int[] ww = new int[w.length + 1];
            System.arraycopy(w, 0, ww, 0, w.length);
            ww[ww.length - 1] = (int)(k & 1073741823L);
            w = ww;
         }
      }

      return w == val ? null : w;
   }

   private Bignum(int[] valueArray) {
      this.value = valueArray;
      this.negative = false;
   }

   private static int[] mul0(int[] u, int[] v, int[] x) {
      int[] w = x;

      int n;
      for(n = u.length - 1; u[n] == 0; --n) {
      }

      int m;
      for(m = v.length - 1; v[m] == 0; --m) {
      }

      if (m >= 0 && n >= 0) {
         long k = 0L;
         int q = 0;
         int maxpos = 0;
         if (x == null || x.length < n + m + 3) {
            w = new int[n + m + 3];
         }

         for(int j = 0; j <= n; ++j) {
            k = 0L;
            q = j;

            for(int i = 0; i <= m; ++i) {
               long uv = (long)u[j];
               long t = uv * (long)v[i] + (long)w[q] + k;
               w[q++] = (int)(t & 1073741823L);
               k = t >> 30;
            }

            while(k != 0L) {
               long uv = (long)w[q] + k;
               w[q++] = (int)(uv & 1073741823L);
               k = uv >> 30;
            }

            if (q > maxpos) {
               maxpos = q;
            }
         }

         return w;
      } else {
         if (x == null) {
            w = new int[1];
         }

         w[0] = 0;
         return w;
      }
   }

   static {
      smallPrimes[0] = 2;
      smallPrimes[1] = 3;
      smallPrimes[2] = 5;
      smallPrimes[3] = 7;
      smallPrimes[4] = 11;
      smallPrimes[5] = 13;
      smallPrimes[6] = 17;
      smallPrimes[7] = 19;
      smallPrimes[8] = 23;
      smallPrimes[9] = 29;
      smallPrimes[10] = 31;
      smallPrimes[11] = 37;
      smallPrimes[12] = 41;
      smallPrimes[13] = 43;
      smallPrimes[14] = 47;
      smallPrimes[15] = 53;
      smallPrimes[16] = 59;
      smallPrimes[17] = 61;
      smallPrimes[18] = 67;
      smallPrimes[19] = 71;
      smallPrimes[20] = 73;
      smallPrimes[21] = 79;
      smallPrimes[22] = 83;
      smallPrimes[23] = 89;
      smallPrimes[24] = 97;
      smallPrimes[25] = 101;
      smallPrimes[26] = 103;
      smallPrimes[27] = 107;
      smallPrimes[28] = 109;
      smallPrimes[29] = 113;
      smallPrimes[30] = 127;
      smallPrimes[31] = 131;
      smallPrimes[32] = 137;
      smallPrimes[33] = 139;
      smallPrimes[34] = 149;
      smallPrimes[35] = 151;
      smallPrimes[36] = 157;
      smallPrimes[37] = 163;
      smallPrimes[38] = 167;
      smallPrimes[39] = 173;
      smallPrimes[40] = 179;
      smallPrimes[41] = 181;
      smallPrimes[42] = 191;
      smallPrimes[43] = 193;
      smallPrimes[44] = 197;
      smallPrimes[45] = 199;
      smallPrimes[46] = 211;
      smallPrimes[47] = 223;
      smallPrimes[48] = 227;
      smallPrimes[49] = 229;
      smallPrimes[50] = 233;
      roundingValue = 4;
      ZERO = new Bignum("0,0");
      ONE = new Bignum(1, 0);
      TWO = new Bignum(2, 0);
   }
}